\documentclass{iccmemoria}

\titulo{Diseño e Implementación de algoritmos para la captura y decodificación de códigos de barra QR Code en dipositivos móviles}
\author{Luis Eduardo González Martínez}
\supervisor{Benjamin Ingram}
\informantes{}{}
\adicional{}
\date{}
\usepackage{graphicx}
\usepackage{amssymb}

\begin{document}
\renewcommand{\listtablename}{Índice de tablas}
\renewcommand{\tablename}{Tabla~}

\maketitle

%dedicatoria

%\begin{dedicatory}
%	Dedicatoria
%\end{dedicatory}

%agradecimientos
%\begin{acknowledgment}
%\end{acknowledgment}

\tableofcontents
\listoffigures
%\listoftables

%\begin{resumen}
%\end{resumen}


%\begin{abstract}
%\end{abstract}


\chapter{Introducción}
\section{Descripción}
	Los códigos de barra aparecen cada vez con más frecuencia en nuestro diario vivir, un claro ejemplo de ello, son las tiendas o supermercados, cada producto que ahí se encuentra es etiquetado con un código de barra, el cual permite obtener la especificación única del producto.\\
	El problema aparece al momento de leer este código para obtener su información, puesto que en muchas ocasiones, se necesitan instrumentos adecuados para su correcta lectura, además de software que permita captar y procesar la información.\\
	Las cámaras pueden ser utilizadas para identificar objetos, es decir, si las imágenes presentan un código de barra en una superficie visible, entonces un sistema con una cámara portátil podría reconocerlo y proporcionar al usuario la información que mantiene codificada.\\
	Por todo lo anterior, este proyecto pretende ofrecer una herramienta que permita localizar un código de barra dentro de una imagen, para su posterior decodificación.\\
	Existe una gran variedad de códigos de barras, pero este proyecto está enfocado en un tipo en especial, llamado QR Code (Quick Response Code). QR Code que es un tipo de código de dos dimensiones que está teniendo un gran impacto en los sistemas de información, permitiendo obtener muchos datos en muy poco tiempo.\\
\begin{figure}
  \centering
    \includegraphics[width=4cm]{Codigo_QR.eps}
  \caption{Código QR que dice: Ojalá vivas tiempos interesantes}
  \label{fig:QR Code Ejemplo}
\end{figure}

%http://es.wikipedia.org/wiki/Archivo:Codigo_QR.svg  faltan las referencias.
\newpage
	Estos códigos se pueden utilizar en distintos tipos de tareas, tales como, aceder a un enlace Web, realizar una llamada telefónica, enviar un Email, añadir un contacto telefónico, navegar en Google Maps a un punto de interés, realizar una búsqueda en Internet, etc. Las cuales pueden ser útiles para una gran variedad de negocios.\\	
	La herramienta propuesta pretende aumentar las probabilidades de decodificación del sistema, aplicando técnicas de procesamiento de imágenes, supliendo la limitante de sistemas actuales que no corrigen el error del usuario al momento de capturar la imagen con un ángulo, rotación o inclinación indebida; provocando errores, demoras en la decodificación, por tener que hacer la captura nuevamente, y más importante, la pérdida de la información que contiene el código.

\section{Contexto}
	Al realizar captura de imágenes con dispositivos móviles, éstas pueden verse afectadas por el pulso de la persona que captura, esto produce que el código de barra aparezca con un cierto grado de rotación, inclinación o que el código esté en una imagen más amplia, que no esté enfocada precisamente en el código de barra a decodificar.	
\section{Alcance}
		El proyecto pretende alcanzar una probabilidad más alta de decodificación de códigos de barra QR Code, aplicando algoritmos avanzados de procesamiento de imágenes, logrando capturar la imagen, analizarla, decodificarla y entregando el resultado de la decodificación al usuario, a través de la interfaz de la aplicación.\\
	Una de las limitantes más grandes para este proyecto es el escaso poder de procesamiento que poseen los dispositivos móviles, en este proyecto específico los teléfonos celulares, limitando el procesamiento de imágenes por el tiempo que esto podría tomar.
\section{Objetivo general}
	Desarrollar una aplicación en Java para dispositivos móviles que sea capaz de interpretar un símbolo QR Code 2006 compatible y decodificar su mensaje. Ademas implementar algoritmos de tratamiento de imágenes para mejorar el éxito en la decodificación.
\section{Objetivos específicos}
\begin{itemize}
\item Investigar plataformas y el lenguaje de programación para dispositivos móviles.
\item Implementar algoritmos de captura de imágenes.
\item Investigar algoritmos de procesamiento de imágenes para resolver problemas de ángulos e inclinación en la imagen.
\item Implementar algoritmos de procesamiento de imágenes para decodificar códigos QR Code.
\item Hacer comparación de resultados utilizando los distintos algoritmos y buscar posibles combinaciones que entreguen un mejor resultado.
\item Escribir memoria.
\end{itemize}
	
%\section{Delimitación}
	

\chapter{Marco Teórico}
%El objetivo del presente capítulo es definir los conceptos teóricos que permitan avalar las propuestas de esta memoria.
El código bidimensional QR Code se define en la norma ISO 18004, la cual describe en su totalidad las partes y procesos que se realizan para obtener alguna versión del código. Es por esto que se debe estudiar en su totalidad todo lo que concierne a este código. Además se revisarán algoritmos de procesamiento de imágenes, que se utilizaran para desarrollar el objetivo de esta memoria.
\section{¿Qué es QR Code?}

QR Code o Quick Response Code (Código de Respuesta Rápida), es un estándar de
“código de barras bidimensional”.\\
Se creo en el año 1994, por la empresa japonesa Denso Wave. Esta empresa distribuye las especificaciones del QR Code en forma gratuita, aún cuando posee una patente de este código, pero no ejerce los derechos de esta.
Existen dos estándares para la descripción del QR Code, El estándar japonés JIS X 0510, redactado en japonés y distribuido el año 1999 y el estándar de la ISO, ISO/IEC 18004, aprobado en junio del año 2000 y revisado el 2006.\\
\\
El éxito del uso de este tipo de código, es su estándar abierto y lo fácil de la decodificación en cualquier teléfono móvil que cuente con una cámara, sin  importar la calidad de ésta.\\
En Japón es muy utilizado este código y es muy raro que los teléfonos móviles no vengan con un software incorporado para decodificarlos.

\subsection{Ventajas del QR Code}
% sacado de http://www.denso-wave.com/qrcode/aboutqr-e.html
QR Code (Código 2D) contiene información en las direcciones vertical y horizontal, mientras que un código de barras contiene datos en una sola dirección. Por lo tanto el código QR Code tiene un volumen mucho mayor de información que un código de barras.\
Este código posee características de almacenamiento de datos que lo diferencian de sus principales competencias, puesto que, es capaz de almacenar hasta 7.089 dígitos, 4.296 caracteres alfanuméricos, 2.953 números binarios y además tiene la particular capacidad de almacenar 1.817 caractéres Kanji que son las letras del alfabeto japonés.

\begin{figure}
  \centering
    \includegraphics[width=8cm]{comparacionCodigos.eps}
  \caption{Comparación de Códigos de barra de una y dos dimensiones}
  \label{fig:Comparacion}
\end{figure}

\subsection{Corrección de Errores}
Los códigos QR Code tienen la capacidad de corregir errores para restaurar los datos si el código se encuentra sucio o dañado.
Existen 4 niveles de corrección de errores, llegando a recuperar hasta un 30\% de la información perdida debido a la suciedad o daño del código.
%falta imagen con la descripcion de los errores aunque no es necesario


\subsection{Otras Características}
Los códigos QR Code pueden ser leídos a gran velocidad, puesto que poseen patrones localizadores que ayudan a detectar su posición. Así la posición del código no es crítica a diferencia de los códigos de barra de una dimensión que necesitan estar alineados horizontalmente.\\
%foto con los patrones resaltados
%http://www.denso-wave.com/qrcode
Existen otros códigos bidimensionales, como el DataMatrix que tambien está estandarizado. La diferencia con el QR Code y los demás códigos es la velocidad a la que se decodifica, de ahí el nombre de Quick Response (QR).\\
Además no es necesario que la imagen tomada sea de gran calidad, puesto que se pierde espacio para almacenar datos.

\section{Resumen del estándar de QR Code.}
\subsection{Términos y Definiciones}
Definición de los principales términos del estándar QR Code.\\
\begin{itemize}

\item \textbf{Contador de Caracteres:}
Secuencia de bits que define la longitud de la cadena de datos en un modo.

\item \textbf{Enmascarado de Datos:}
 Proceso por el cual se realiza la operación XOR, con un patrón de máscara, a los módulos de la región de codificación, esto aumenta la diferencia entre módulos blancos y negros mejorando la decodificación.

\item \textbf{Patrón de referencia de la máscara de datos:} 
Tres bits identifican el patrón de la máscara de datos en el símbolo.

\item \textbf{Región de Codificación:}
 Región del símbolo no ocupada por los patrones de funcionamiento y disponible para la codificación de datos, corrección de errores, identificación de la versión del código y el formato del mismo.
 
\item \textbf{Formato de la Información:} 
 Patrón codificado que contiene la información sobre las características del símbolo, el grado de corrección de errores con el que se han encriptado los datos y el tipo de máscara que se les ha aplicado.

\item \textbf{Patrón de alineación:}
Permite resincronizar las coordenadas de mapeo de la imagen QR Code ante posibles distorsiones moderadas del área.

\item \textbf{Patrón de Función:}
Parte del símbolo que no contiene datos codificados, sino la información necesaria para hacer el proceso de decodificación de los datos. Los patrones de función son: patrón de localización, separador, patrón de alineamiento y patrón temporizador.

\item \textbf{Modo:}
Método en el que se representa un conjunto de datos como una cadena de bits. Estos datos pueden ser del tipo: alfanuméricos, numéricos, bytes, kanji o cualquier otro que se pueda definir.

\item \textbf{Indicador de Modo:}
Cuatro bits que indican el modo con el que se ha codificado la información de los siguientes datos.

\item \textbf{Bit de relleno:}
Bits que se usan para rellenar una palabra después del terminador para obtener un número fijo de datos en cada bloque de datos del código.

\item \textbf{Patrón Localizador:}
Son tres patrones que sirven para calcular la orientación rotacional del código. Estos patrones se encuentran en las esquinas superiores e inferior izquierda.

\item \textbf{Bits Restantes:}
Usados para rellenar algunas posiciones de la región codificada donde el espacio no se divide en 8 bits.

\item \textbf{Palabra Códificada (Codeword):}
Conjunto de 8 módulos que pueden tener diferentes formas dependiendo de su localización en el símbolo y que sirve para almacenar información codificada de los datos o de la corrección de errores.

\item \textbf{Palabra Códificada Restante:}
Codeword para rellenar posiciones sin codeword asignados, completan la capacidad total del código.


\item \textbf{Módulo:}
Cuadro blanco o negro que en conjunto definen un QR Code.

\item \textbf{Separador:}
Patrón de función formado por módulos blancos; tiene un ancho de un módulo y separa los patrones localizadores del resto del código.

\item \textbf{Terminador:}
Patrón de bits ceros de un número definido, en función del código, que se usa para poner fin a la cadena de bits que representan datos.

\item \textbf{Versión:}
Tamaño del código que puede ir de la versión 1 de 21x21 módulos hasta 40 de 177x177 módulos. 

\item \textbf{Zona de silencio:}
Zona que rodea al código de color blanco que permite delimitar sus bordes, debe ser al menos de 4 módulos.ncronizar las coordenadas de mapeo de la imagen QR Code ante posibles distorsiones moderadas del área.


\end{itemize}


\subsection{Características Principales}

Los códigos QR Code tienen 40 versiones y 4 grados para corregir errores (L,M,Q,H). Así un código 40-H se puede decir que es de la versión 40 y su grado de corrección de errores es H. Cada versión tiene un tamaño siendo la 1 de 21x21 módulos y 40 de 177x177 módulos la más grande, aumentando en 4 módulos cada versión.\\

Formato de los datos a codificar.
\begin{itemize}
\item Datos numéricos (0-9).
\item Datos alfanuméricos (0-9, A-Z y otros 9 caractéres: espacio,\$,\%,*,+,-,.,/,:).
\item bytes (por defecto ISO/IEC 8859-1).
\item Caractéres Kanji, compactados en 13 bits (caractéres del alfabeto japonés).
\end{itemize}

Para un código de versión 40-L, el número máximo de datos que puede contener es:
\begin{itemize}
\item Datos numéricos: 7089 caractéres.
\item Datos alfanuméricos: 4296 caractéres.
\item Bytes: 2953 caractéres.
\item Caractéres Kanji: 1817 caractéres.
\end{itemize}

La corrección de errores se basa en Reed Solomon y tiene 4 niveles.

%falta referencia para reed-solomon

\begin{itemize}
\item L (low) bajo, puede corregir hasta el 7\% de los corewords del código.
\item M (medium) medio, puede corregir hasta el 15\% de los codewords del código.
\item Q (quality) calidad, puede corregir hasta el 25\% de los codewords del código.
\item H (high) alto, puede corregir hasta el 30\% de los codewords del código.
\end{itemize}

Los módulos del código pueden ser blancos o negros y representan respectivamente el 0 y el 1 binario.
%mostrar imagen del codigo

\subsection{Estructura del Código}
Los QR Code están formados por módulos colocados en una estructura cuadrada. Ésta estructura contiene la región de codificación y los patrones de función que son: patrón localizador, separador, patrón temporizador y patrón de alineamiento. El código debe estar rodeado por una zona de silencio.



%imagen sacada de la ISO
\begin{figure}[h]
  \centering
    \includegraphics[width=10cm]{estructura.eps}
  \caption{Estructura de un código QR Code versión 7}
  \label{fig:Estructura}
\end{figure}

Las versiónes, además del tamaño, se diferencian por el número de codewords que contienen y el patrón de alineamiento, algunas versiones tienen bits de relleno y otras no y las versiones anteriores a la 7 no tienen información de la versión. La versión 1 no tiene patrones de alineamiento. Todas la versiones tienen los tres patrones localizadores, dos patrones temporizadores, tres separadores y la información de formato por duplicado.

El patrón localizador se sitúa en las esquinas superior izquierda, superior derecha e inferior izquierda del código QR Code. Está formado por un cuadro de 3x3 de módulos negros, el cual esta rodeado por un cuadro de 5x5 de módulos blancos a su vez rodeado por otro cuadro de 7x7 de módulos negros. Encontrar este patrón será muy difícil dentro de otras partes del código lo que hace improbable que se provoquen errores por este motivo.

%imagen sacada de la ISO
\begin{figure}[h]
  \centering
    \includegraphics[width=8cm]{patronlocalizador.eps}
  \caption{Estructura de un código QR Code versión 7}
  \label{fig:Patron Localizador}
\end{figure}

Los separadores están formados por módulos blancos y rodean los bordes de los patrones localizadores que dan a la parte interior del símbolo.

Los patrones temporizadores son dos, uno vertical y otro horizontal. Están formados por una línea de módulos de color alternados, comenzando y terminando en un módulo negro. Son usados para obtener la versión del código y para que las coordenadas de los módulos puedan ser determinadas. El patrón temporizador horizontal cruza la fila número 6 entre los separadores superiores y el vertical igual pero cruzando la columna 6.

Los patrones de alineamiento están formados por un módulo negro, rodeado de un cuadro de 3x3 de módulos blancos, el cual esta rodeado por otro cuadro de 5x5 de módulos negros. El número de estos patrones varía según la versión del código.

La región de codificación contiene los codewords que representan los datos, también contiene codewords para la corrección de errores, la información de formato y la información de versión en la mayoria de los casos.




\begin{center}
   \begin{tabular}{| l | p{2cm} | p{2cm} | p{2cm} | p{2cm} | p{2cm} | p{2cm} |}  
   \hline
Versión & Número de módulos por lado & Módulos de patrones de función &Módulos de información de formato y versión& Módulos de datos&Codewords de datos&Bits restantes\\ \hline
1 & 21 & 202 & 31 & 208 & 26 & 0 \\ \hline
2 & 25 & 235 & 31 & 359 & 44 & 7 \\ \hline
3 & 29 & 243 & 31 & 567 & 70 & 7 \\ \hline
4 & 33 & 251 & 31 & 807 & 100 & 7\\ \hline
5 & 37 & 259 & 31 & 1079 & 134 & 7\\ \hline
6 & 41 & 267 & 31 & 1383 & 172 & 7\\ \hline
7 & 45 & 390 & 67 & 1568 & 196 & 0\\ \hline
8 & 49 & 398 & 67 & 1936 & 242 & 0\\ \hline
9 & 53 & 406 & 67 & 2336 & 292 & 0\\ \hline
10 & 57 & 414 & 67 & 2768 & 346 & 0\\ \hline
11 & 61 & 422 & 67 & 3232 & 404 & 0\\ \hline
12 & 65 & 430 & 67 & 3728 & 466 & 0\\ \hline
13 & 69 & 438 & 67 & 4256 & 532 & 0\\ \hline
14 & 73 & 611 & 67 & 4651 & 581 & 3\\ \hline
15 & 77 & 619 & 67 & 5243 & 655 & 3\\ \hline
16 & 81 & 627 & 67 & 5867 & 733 & 3\\ \hline
17 & 85 & 635 & 67 & 6523 & 815 & 3\\ \hline
18 & 89 & 643 & 67 & 7211 & 901 & 3\\ \hline
19 & 93 & 651 & 67 & 7931 & 991 & 3 \\ \hline
20 & 97 & 659 & 67 & 8683 & 1085 & 3\\ \hline
21 & 101 & 882 & 67 & 9252 & 1156 & 4\\ \hline
22 & 105 & 890 & 67 & 10068 & 1258 & 4\\ \hline
23 & 109 & 898 & 67 & 10916 & 1364 & 4\\ \hline
24 & 113 & 906 & 67 & 11796 & 1474 & 4\\ \hline
25 & 117 & 914 & 67 & 12708 & 1588 & 4\\ \hline
26 & 121 & 922 & 67 & 13652 & 1706 & 4\\ \hline
27 & 125 & 930 & 67 & 14628 & 1828 & 4\\ \hline
28 & 129 & 1203 & 67 & 15371 & 1921 & 3\\ \hline
29 & 133 & 1211 & 67 & 16411 & 2051 & 3\\ \hline
30 & 137 & 1219 & 67 & 17483 & 2185 & 3\\ \hline
31 & 141 & 1227 & 67 & 18587 & 2323 & 3 \\ \hline
32 & 145 & 1235 & 67 & 19723 & 2465 & 3\\ \hline

   \end{tabular}
 \end{center}
 
\begin{center}
   \begin{tabular}{| l | p{2cm} | p{2cm} | p{2cm} | p{2cm} | p{2cm} | p{2cm} |}  
   \hline 
   33 & 149 & 1243 & 67 & 20891 & 2611 & 3\\ \hline
34 & 153 & 1251 & 67 & 22091 & 2761 & 3\\ \hline
35 & 157 & 1574 & 67 & 23008 & 2876 & 0\\ \hline
36 & 161 & 1582 & 67 & 24272 & 3034 & 0\\ \hline
37 & 165 & 1590 & 67 & 25568 & 3196 & 0\\ \hline
38 & 169 & 1598 & 67 & 26896 & 3362 & 0\\ \hline
39 & 173 & 1606 & 67 & 28256 & 3532 & 0\\ \hline
40 & 177 & 1614 & 67 & 29648 & 3706 & 0\\ \hline 
  \end{tabular}
 \end{center}
\section{Proceso de Codificación.}

El proceso de codificación se puede dividir en 7 pasos.

\begin{enumerate}

\item {\bf Análisis de Datos.}
Se analizan los datos a codificar identificando de qué tipo son sus caractéres, para calcular en que modos codificarlos. El estándar soporta varios modos de codificación, pudiendo usarse a la vez diferentes modos para cada subconjunto de caractéres. Si no se especifíca la versión a usar, se debe usar la menor versión necesaria.
\item {\bf Codificación de datos.}
Se convierten los datos en una cadena de conjunto de bits dependiendo del modo usado. Se inserta un indicador de modo delante de cada subconjunto de datos y un terminados al final del mismo para saber en qué modo están codificados y dónde termina el subconjunto. Finalmente se dividen los datos en codewords de 8 bits.
\item {\bf Codificación de corrección de errores.}
Se ejecuta el algoritmo de corrección de error, para generar los codewords de corrección de errores. Éstos se añaden al final de los codewords de datos.
\item {\bf Estructura final del mensaje.}
Se entrelazan los codewords de datos y de corrección de error y se añaden los bits de relleno si es necesario.
\item {\bf Colocación de Módulos en el código.}
Se colocan los módulos de los codewords en el código QR Code junto a los patrones de función para formar un símbolo QR Code.
\item {\bf Enmascarar los datos.}
Se aplican los patrones de enmascarado de datos a la región de codificación. Se evalúan los resultados y se selecciona el patrón que optimice el balance entre módulos blancos y negros y minimice la aparición de patrones indeseados.
\item {\bf Formato y versión de formato.}
Generar la información de formato y la de versión si es necesario y colocarla en el símbolo para completarlo.
\end{enumerate}


\subsection{Análisis de los Datos.}
Los datos que se codifican pueden tener diferentes formatos, además pueden dividirse en conjunto de datos que tienen diferentes tipos o tamaños. Los datos se analizan para ver su formato y encontrar el modo apropiado para codificarlos. Se puede cambiar el modo para optimizar el espacio dentro del código. Se puede hacer la codificación más eficiente si el dato se codifica en el modo que requiere menos bits por carácter, teniendo en cuenta el espacio de la cabecera. La cabecera está compuesta del indicador de modo y el contador de caractéres y se sitúa delante de cada subconjunto de datos. Si el conjunto es pequeño no se codifica en cualquier modo, dado que no vale la pena codificar en un modo específico un pequeño conjunto. Además, si el código QR Code aumenta su capacidad en una forma discreta en cada versión, no es necesario alcanzar siempre la eficiencia máxima.\\

Los modos en los cuales se pueden encontrar los datos son los siguientes:
\begin{itemize}
\item \textbf{Modo Númerico.}\\
Se codifican los caractéres numéricos del conjunto [0-9]. Generalmente, 3 caractéres se representan con 10 bits en este modo.

\item \textbf{Modo Alfanumérico.}\\
Se codifica un conjunto de 45 caractéres. Los cuales son: 10 dígitos del modo numérico, 26 caractéres del alfabeto internacional y 9 símbolos más (espacio, \$, \%, *, +, -, . , /,:). Dos caractéres alfanuméricos se representan con 11 bits en este modo.
\item \textbf{Modo Byte.}\\
Los datos se codifican con 8 bits por carácter en código ASCII.

\item \textbf{Modo Kanji.}\\
Codifica los caractéres Kanji del alfabeto japonés de acuerdo con el sistema Shift Jis basado en JIS X 0208. Cada carácter de dos bytes es compactado en un codeword de 13 bits.

\item \textbf{Modo Interpretación de canal extendido (ICE).}\\
Permite especificar interpretaciones particulares de un modo para crear un conjunto de caractéres particular.
\end{itemize}


\subsection{Codificación de Datos.}
Los datos son convertidos en un flujo de bits consistente en uno o más subconjuntos de modos diferentes. Utilizando el ICE por defecto, el flujo de bits inicia con el primer indicador de modo. Si se utiliza más ICEs diferentes, el flujo comenzará con la cabecera ICE, seguida del primer subconjunto de datos y así sucesivamente hasta completar el código.\\

La cabecera ICE se compone de un indicador de modo de 4 bits y un designador de CE que puede ser de 8, 16 ó 24 bits. Esta cabecera empieza con el bit más significativo del indicador de modo y termina con el menos significativo del designador ICE.\\
 
Los subconjuntos tienen un tamaño de 4 bits y se componen de un indicador de modo, un contador de caractéres y los datos almacenados. Además cada subconjunto de modo empieza con el bit más significativo del indicador de modo y termina con el bit menos significativo del flujo de datos. Entre los subconjuntos no existen separadores ya que su tamaño y lugar de inicio están delimitados inequívocamente por el indicador de modo y el contador de caractéres.\\

Los indicadores tendrán la siguiente representación en bits.\\
- Numérico = 0001\\
- Alfanumérico = 0010\\
- Byte = 0100\\
- Kanji = 1000\\
- ICE = 0111\\
- Fin de mensaje = 0000\\
% falta tabla del contador de caracteres


Cuando se coloca el último subconjunto de modo se agrega un terminador de fin de mensaje, que es de 4 bits ceros. En algunas ocasiones puede ser omitido, si la capacidad restante del código es menor.\\

En el modo numérico, los datos se dividen en grupos de tres dígitos, cada grupo se convierte en binario de 10 bits. Si el número de dígitos no es múltiplo de tres, se convierten en 4 ó 7 bits, si esque son uno o dos dígitos respectivamente. Finalmente los datos transformatos en binarios son concatenados y además se les agrega el indicador de modo al inicio y el contador de caractéres al final.\\

En el modo alfanumérico, primero a cada caractér se le asigna un valor entre 0 y 44 según la siguiente tabla:

%tabla 



\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
C&V&C&V&C&V&C&V&C&V&C&V&C&V&C&V\\ \hline
0&0&6&6&C&12&I&18&O&24&U&30&SP&36&.&42\\ \hline
1&1&7&7&D&13&J&19&P&25&V&31&\$&37&/&43\\ \hline
2&2&8&8&E&14&K&20&Q&26&W&32&\%&38&:&44\\ \hline
3&3&9&9&F&15&L&21&R&27&X&33&*&39&&\\ \hline 
4&4&A&10&G&16&M&22&S&28&Y&34&+&40&&\\ \hline 
5&5&B&11&H&17&N&23&T&29&Z&35&-&41&&\\ \hline 
\end{tabular}








Los subconjuntos se agrupan de a dos caractéres codificados en 11 bits. El valor del primer carácter se multiplica por 45 y a ésto se le suma el valor del segundo caracter. La suma es convertida en un número de 11 bits. Si el número de caractéres no es múltiplo de dos se convierte en un número binario de 6 bits. Finalmente los datos binarios son concatenados y se les agrega al inicio el indicador de modo y el contador de caractéres.\\

En el modo Byte, el valor de cada caracter es el mismo que el de su correspondiente codeword de 8 bits. Esto quiere decir que cada carácter  se codifica en 8 bits y que un carácter ocupa exactamente un codeword. Finalmente los datos binarios son concatenados y se les agrega al inicio el indicador de modo y el contador de caractéres.\\

Existe una posibilidad de poder combinar varios modos de codificación para los datos, y así ahorrar espacio. Cada segmento de datos se codificaría con los modos que se indicaron y posteriormente se concatenarían empezando cada subconjunto con el indicador de modo y el contador de caractéres.\\

Al final de los subconjuntos se añade un terminador. El terminador se puede omitir si el espacio no alcanza para éste.


\textbf{Conversión del flujo de bits a codeword.}\\
Ahora los datos codificados se dividen en grupos de 8 bits llamados codewords. En el caso que no sean múltiplos de ocho se añadirán bits de relleno al último codeword. Luego, el mensaje resultante debe ser completado  con codewords de relleno hasta rellenar la capacidad máxima de codewords de la versión de QR Code del código que se está codificando. Estos codewords de relleno son 11101100 y 00010001 que se van añadiendo alternadamente. Terminado esto se añadirán los codewords de corrección de errores como se muestra en el siguiente punto.
% faltan tablas aunque podria dejarlas como anexo nomas
\subsection{Codificación de corrección de errores.}
QR Code utiliza codificación de control de errores de Reed-Solomon para detectar errores. Para ésto se utilizan una seria de codewords de corrección de errores, que se agregan a los datos codificados. Existen cuatro niveles de corrección de errores los cuales son:\\
\begin{itemize}
\item \textbf{L} (Low) con 7 \% de capacidad de recuperación.
\item \textbf{M} (Medium) con 15 \% de capacidad de recuperación.
\item \textbf{Q} (Quality) con 25 \% capacidad de recuperación.
\item \textbf{H} (High) con 30 \% capacidad de recuperación.
\end{itemize}

Este sistema puede corregir dos tipos de errores, cuando un caracter nose puede decodificar (borrón) y cuando se decodifica en un caracter erróneo. Existe una fórmula que relaciona el número de borrones y errores corregibles en un codeword de corrección de errores.\\\\


\begin{equation}
e + 2t \leq d - p\\
\end{equation}

donde:\\
e = número de borrones.\\
t = número de errores.\\
d = número de codewords de corrección de errores.\\
p = número de codewords de protección de QR Code.\\



\subsection{Estructura final del mensaje.}
Se divide la secuencia de codewords en n bloques. Para cada bloque se generan los codewords de corrección de errores. Luego se crea la secuencia final de codewords que tiene el siguiente orden:
Codeword de datos 1 de bloque 1, codeword de datos 1 de bloque 2, codeword de datos 1 de bloque 3, ... , codeword de datos 1 de último bloque, codeword de datos 2 de bloque 1, ... , codeword de datos 2 de último bloque, ... , último codeword de datos de bloque 1, ... , último codeword de datos de último bloque, codeword de error 1 de bloque 1, codeword de error 1 de bloque 2, ... , codeword de error 1 de último bloque, ... , último codeword de error de bloque 1, ... , último codeword de error de último bloque.

\subsection{Colocación de módulos en el código.}
La gran mayoría de los codewords se representan en el código como un bloque de 2x4 ó 4x2 módulos. Aunque algunos tendrán formas irregulares por estar en lugares cercanos a algún patrón de función, como muestra la figura.

\begin{figure}[h]
  \centering
    \includegraphics[width=3cm]{formacodeword.eps}
  
  \label{fig:Forma Codeword}
\end{figure}

Se debe crear una matriz en blanco con el tamaño que corresponde a la versión del código a crear. Además hay que agregar la región de silencio que rodea al código y que debe ser de 4 módulos de tamaño. Se agregan los tres patrones temporizadores, que tienen un tamaño distinto dependiendo de la versión.

La región de codificación se completa con los codewords, comenzando por la parte inferior derecha del código y subiendo hacia arriba hasta llegar al patrón localizador, y después se pasa a la columna adyacente de la izquierda y bajamos hasta llegar al final, para luego volver a subir. Los codewords quedan dispuestos en zig-zag. Cuando la capacidad máxima del código no se llena con los codewords, se rellena con 3, 4 ó 7 bits de relleno. En la figura se muestra la colocación de codewords en un código de versión 2.

\begin{figure}[h]
  \centering
    \includegraphics[width=10cm]{colocacioncodeword.eps}
  
  \label{fig:colocacion}
\end{figure}

\subsection{Enmascarar los datos.}

Para que la decodificación del QR Code mejore es recomendable que el número de módulos blancos y negros sea equillibrado. Se debe evitar el patrón 1011101 ya que se puede confundir con el patrón localizador. Para lograr el equilibrio se debe aplicar una máscara de datos. Esta máscara no se aplica a los patrones de función, la información de formato y la de versión.\\
 A continuación se muestran los posibles patrones y su código para la información de formato.\\
 \begin{center}
\begin{tabular}{|c|l|}
\hline
Código del patrón de máscara de datos & Fórmula\\ \hline
000 & (i + j) mod 2 = 0\\ \hline
001 & i mod 2 = 0\\ \hline
010 & j mod 3 = 0\\ \hline
011 & (i + j) mod 3 = 0\\ \hline 
100 & ((i div 2) + (j div 3)) mod 2 = 0\\ \hline 
101 & (i * j) mod 2 + (i * j) mod 3 = 0\\ \hline
110 & ((i * j) mod 2 + (i * j) mod 3) mod 2 = 0\\ \hline
111 & ((i + j) mod 2 + (i * j) mod 3) mod 2 = 0\\ \hline 
\end{tabular}
\end{center}

\subsection{Formato y versión de formato.}
\subsubsection{Información de Formato.}
La información de formato tiene un tamaño de 15 bits, de los cuales 5 contienen datos y los otros 10 con para recontruir los 5 anteriores en caso de error al decodificar. Para esto se utiliza (15,5) BCH Code.%falta la referecia del paper

De los 5 primeros bits, dos indicn el nivel de corrección de errores usado.\\
L = 01, M = 00, Q = 11, H = 10.\\
Los otros tres bits indican el patrón de máscara utilizado.\\
Cuando los 15 bits se les aplica mediante XOR la máscara 101010000010010, utilizada para evitar que se genere una información de formato compuesta de ceros.\\
Finalmente la información de formato se dispone en la matriz del código por duplicado en las zonas establecidas para esto. La siguiente figura ilustra lo anterior.

\begin{figure}[h]
  \centering
    \includegraphics[width=7cm]{formatoinformacion.eps}
  \label{fig:Formato Informacion}
\end{figure}

\subsubsection{Información de Versión.}
La información de versión se aplica a códigos de versión superior a 7. Se conforma de 18 bits, donde los 6 primeros son de datos y los otros 12 son para corregir errores. Los errores se corrigen mediante (18,6) BHC Code. Los 6 bits de datos contienen la versión del código codificada con el simbolo más significativo primero. Por ejemplo 000111 representa la versión 7, 101000 representa la versión 40. Esta información no es necesario enmascarar, dado que este proceso produciría algunas cadenas de ceros que no tienen información de la versión.\\
La información de la versión se dispone en la matriz del código por duplicado en las zonas establecidas para esto. \\

Con la información que se tiene, se puede comenzar con el procesamiento de imágenes para lograr la decodificación del código y finalmente obtener los datos encriptados en éste.


\section{Procesamiento de Imágenes.}

\subsection{Reconocimiento de Bordes.}
El objetivo de la detección de bordes, en general, es reducir significativamente la cantidad de datos en una imagen y al mismo tiempo conservando las propiedades estructurales se se utilizará para el procesamiento de la imagen. Existen varios algoritmos para hacer esta tarea, pero el mas usado es el algoritmo de Canny, a pesar que es antiguo se sigue utilizando en investigación.\\
Los criterios usados por este algoritmo son:\\
\begin{enumerate}
\item Detección: Evita la eliminación de bordes importantes y no suministrar falsos bordes.
\item Localización: La distancia entre la posición real y la localizada del borde debe ser minima.
\item Número de respuestas: Intagra las respuestas múltiples correspondientes a un único borde.
\end{enumerate}

\subsubsection{Algoritmo de Canny}
El cálculo de la primera derivada es uno de los métodos relacionados con la detección de bordes, que es usada porque toma el valor de cero en las regiones donde no hay variación en la intensidad y tiene un valor constante en la transición de intensidad. Esto hace que en un cambio de intensidad se manifiesta en un cambio brusco en la primera derivada, lo que es usado para detectar el borde.\\

El algoritmo de canny consiste en tres grandes pasos:

\begin{enumerate}
\item Obtener el gradiente: Se calcula la magnitus y orientación del vector en cada píxel.
\item Supresión no máxima: Adelgazamiento del ancho de los bordes obtenidos con el gradiente, hasta lograr bordes de un píxel de ancho.
\item Histéresis de umbral: Aplicación de función de histéresis basada en dos umbrales, con esto se reduce la posibilidad de contornos falsos.
\end{enumerate}

\subsubsection{Obtener el Gradiente.}
Para obtener el gradiente, lo primero que se realiza es un filtro gaussiano a la imagen original, con el objetivo de suavizar la imagen y tratar de eliminar el ruido que exista. Esto puede presentar el problema que el suavizado sea excesivo, lo que conlleva en la perdida de detalles de la imagen y altera el resultado final de la operación.\\
A contimuación se muestra una máscara que se puede utilizar para el filtrado gaussiano.\cite{rebaza2007deteccion}\\


\[
A = {1 \over 159}\dot{}\left( \begin{array}{lcccl}
            2 & 4 & 5 & 4 & 2  \\
            4 & 9 & 12 & 9 & 4  \\
            5 & 12 & 15 & 12 & 5\\
            4 & 9 & 12 & 9 & 4  \\
            2 & 4 & 5 & 4 & 2\\
           \end{array}
    \right)
\]
\subsubsection{Supresión no máxima}
La imágen resultante en el paso anterior sirve como entrada para generar una imágen con los bordes adelgazados. Se utilizan cuatro direcciones con las orientaciones de 0, 45, 90 y 135 grados con respecto al eje horizontal. Para cada píxel se encuentra la dirección que mejor se aproxima a la dirección del angulo del gradiente.

\subsubsection{Histéresis de umbral}
Generalmente la imágen que se obtiene contiene máximos locales que se producen por el ruido. Una solución para eliminar este ruido es la histéresis del umbral.\\
Este proceso consiste en tomar la orientación de los puntos de borde de la imágen y tomar dos umbrales, el primero mas pequeño que el segundo.\\
En cada punto de la imágen se localiza el siguiente punto de borde no explorado, este tiene que ser mayor al segundo umbral. A partir de dicho punto seguir las cadenas de máximos locales conectados en ambas direcciones perpendiculares a la normal del borde siempre que sean mayores al primer umbral. Así se marcan todos los puntos explorados y se almacena la lista de todos los puntos en el contorno conectado. 

%\subsection{Reconocimiento de Esquinas.}
%Una esquina se puede definir como la intersección de dos bordes.

%\subsection{Rotación de la Imagen.}


%\section{Proceso de Decodificación de QR Code.}
\chapter{Metodología}
\section{¿Que es una Metodología?}
"Conjunto de métodos que se siguen en una investigación científica o en una exposición doctrinal".% real academia española

\section{Metodología de desarrollo del software.}
Durante el ciclo de vida del software se deben completar una serie de tareas para obtener un producto de software. Además se puede distinguir que distintos componentes del software deben pasar por distintas fases o etapas durante el proceso de desarrollo o ciclo de vida. Cada una de estas tareas se pueden desarrollar y resolver de muchas maneras, con distintas herramientas y usando alguna técnica. Además tenemos que especificar cuándo se termina una tarea, quien debe realizarla, que tareas preceden o anteceden a una dada, que documentación utilizaremos para llevar a cabo esa tarea.\\

Existe una amplia gama de metodologías ágiles que permiten desarrolar softwares, las cuales entregan herramientas que guian en la creación de estos.\\
Algunas de estas metodologías pueden ser:\\
\begin{enumerate}
\item PROGRAMACIÓN EXTREMA o XP: es una metodología ágil centrada en potenciar las relaciones interpersonales como clave para el éxito en desarrollo de software, promoviendo el trabajo en equipo, preocupándose por el aprendizaje de los desarrolladores, y propiciando un buen clima de trabajo.

\item SCRUM: Desarrollada por Ken Schwaber, Jeff Sutherland y Mike Beedle. Define un marco para la gestión de proyectos, que se ha utilizado con éxito durante los últimos 10 años. Está especialmente indicada para proyectos con un rápido cambio de requisitos. Sus principales características se pueden resumir en dos. El desarrollo de software se realiza mediante iteraciones, denominadas sprints y la segunda característica importante son las reuniones a lo largo proyecto.

\item Metodologías Crystal:conjunto de metodologías para el desarrollo de software caracterizadas por estar centradas en las personas que componen el equipo y la reducción al máximo del número de artefactos producidos. El desarrollo de software se considera un juego cooperativo de invención y comunicación, limitado por los recursos a utilizar.

\item Dynamic Systems Development Method  (DSDM): Nace en 1994 con el objetivo de crear una metodología RAD unificada. Sus principales características son: es un proceso iterativo e incremental y el equipo de desarrollo y el usuario trabajan juntos. Propone cinco fases: estudio viabilidad, estudio del negocio, modelado funcional, diseño y construcción, y finalmente implementación.

\item Feature Driven Development (FDD): Define un proceso iterativo que consta de 5 pasos. Las iteraciones son cortas (hasta 2 semanas). Se centra en las fases de diseño e implementación del sistema partiendo de una lista de características que debe reunir el software. 

\end{enumerate}

FDD es una metodología desarrollada alrededor del año 1998 que presenta las características de un proceso ágil. Esta pensado en proyectos con tiempo de desarrollo relativamente cortos(menos de un año). Se basa en un proceso iterativo con iteraciones cortas (2 semanas aproximadamente), que producen un software funcional que el cliente y la dirección de la empresa pueden ver y monitoriar.\\
Las iteraciones se deciden en base a funcionalidades, que son pequeñas partes del software con significado para el cliente.\\

Un proyecto que sigue FDD se divide en 5 fases:\\
\begin{enumerate}
\item Desarrollo de un modelo general.
\item Construcción de la lista de funcionalidades.
\item Plan de releases en base a las funcionalidades a implenentar.
\item Diseñar en base a las funcionalidades.
\item Implementar en base a las funcionalidaades.
\end{enumerate}

La primera actividad consiste en Desarrollar un Modelo General, que actua en paralelo con la construcción de la arquitectura del software. Cuendo se  crea este modelo participan tanto los expertos en el dominio como los desarrolladores. Mediante el esfuerzo de ambas partes se intenta lograr lo que el modelo en espiral proponía con sus primeras iteraciones: un conocimiento global de la aplicación a construir, el entendimiento del negocio en que esta embebida, un primer bosquejo de las features del software, y la definición de restricciones y cuestiones no funcionales. Para esto, se desarrollarán: diagramas de los paquetes, con las clases esenciales y las responsabilidades de las mismas.\\

La segunda actividad, Construir una Lista de funcionalidades, comienza tomando el bosquejo de funcionalidades formulado durante la actividad anterior para refinar las funcionalidades incluidas. Una vez que se han identificado las mismas se las agrupa jerárquicamente para poder estructurar el trabajo de desarrollo; se asignan prioridades segun la satisfacción del cliente – las prioridades sugeridas para las funcionalidades por FDD son: A (debe tener), B (sería útil tener), C (agregar si es posible), o D (futuro); finalmente, se pondera la importancia de cada una para su posterior implementación.\\

La tercera actividad, Planificar por Funcionalidades, toma como input la lista priorizada de la fase anterior y establece los tiempos para las futuras iteraciones. En esta actividad participan el líder de proyecto, el líder de desarrollo y el programador jefe. A medida que se realiza la planificación se delinean los hitos de finalización de las iteraciones, dejando claro cuales son los funcionalidades o conjunto de estas que estarán construidos en dichos hitos. Ademas incluye el encargado de programación.\\

Las últimas dos actividades, Diseñar por Funcionalidades y Construir por Funcionalidad, están relacionadas con la parte productiva del proceso en que se construye la aplicación de manera incremental. Empezando por el diseño que toma las funcionalidades correspondientes a la iteración, el equipo de programadores liderado por el programador jefe identifica las clases, atributos y métodos que realizan la funcionalidad requerida.

%\chapter{Diseño}
%	 En este capítulo se trata la manera en la cual se abordó el problema.

%\chapter{Resultados y Análisis de Resultados}

%\chapter{Conclusiones}

%\section{Trabajo futuro}

%\bibliographystyle{plain} 
%\bibliography{refs}

\chapter{Anexos}
\section{Planificación}

\subsection{Planificación}

\begin{figure}[h]
    \centering
    \includegraphics[width=\textwidth]{planificacion}
    \caption{Planificación de actividades}
    \label{fig:planificacion}
  \end{figure}
  
\end{document}